package leetcode;

import java.util.*;

/**
 * 双栈实现计算器 1
 */
public class MyCalculate {
    /**
     * 设置运算符优先级，优先级越高对应数字越大
     */
    Map<Character, Integer> perv = new HashMap<Character, Integer>() {{
        put('+', 1);
        put('-', 1);
        put('/', 2);
        put('*', 2);
    }};

    public int myCalculate(String s) {
        // 用双端队列表示栈
        Deque<Integer> deque1 = new ArrayDeque<>(); // 存储数字
        Deque<Character> deque2 = new ArrayDeque<>(); // 存储运算符
        List<Character> list = new ArrayList<>(); // 存储s的有效字符串
        // 将不是空格字符的字符添加入list
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!isSpace(c)) {
                list.add(c);
            }
        }
        // 遍历list，遇到数字存入deque1，遇到运算符与deque2的栈顶的运算符优先级作比较若优先级较低先计算栈顶运算符，否则入栈2
        for (int i = 0; i < list.size(); i++) {
            char c = list.get(i);
            if (isNumber(c)) {
                // 是数字要循环到运算符之前获取当前全部数字
                int num = Character.getNumericValue(c);
                while (i < list.size() - 1 && isNumber(list.get(i + 1))) {
                    // 第一种 num * 10 + b
                    int b = Character.getNumericValue(list.get(++i));
                    num = num * 10 + b;
                }
                deque1.push(num);
            } else {
                // 是运算符
                while (!deque2.isEmpty() && perv.get(deque2.peek()) >= perv.get(c)) {
                    // 栈顶元素优先级较大
                    int num2 = deque1.pop();
                    int num1 = deque1.pop();
                    char str = deque2.pop();
                    switch (str) {
                        case '+':
                            deque1.push(num1 + num2);
                            break;
                        case '-':
                            deque1.push(num1 - num2);
                            break;
                        case '/':
                            deque1.push(num1 / num2);
                            break;
                        default:
                            deque1.push(num1 * num2);
                    }
                }
                deque2.push(c);
            }
        }
        // 至此deque2只剩一个元素
        while (!deque2.isEmpty()) {
            if (deque1.size() == 1) {
                // 当前数是一个负数
                char one = deque2.pop();
                if (one == '-') {
                    deque1.push(-deque1.pop());
                }
            }
            int num2 = deque1.pop();
            int num1 = deque1.pop();
            char tmp = deque2.pop();
            switch (tmp) {
                case '+' :
                    deque1.push(num1 + num2);
                    break;
                case '-' :
                    deque1.push(num1 - num2);
                    break;
                case '/' :
                    deque1.push(num1 / num2);
                    break;
                default :
                    deque1.push(num1 * num2);
            }
        }
        return deque1.peek();
    }

    private boolean isSpace(char c) {
        return Character.isSpaceChar(c) ? true : false;
    }

    private boolean isNumber(char c) {
        return Character.isDigit(c) ? true : false;
    }
}

class Test3 {
    public static void main(String[] args) {
        MyCalculate calculate = new MyCalculate();
//        String s = "1 * 2 + 1";
        String s = "1 +2 * 1";
        System.out.println(s + " = " + calculate.myCalculate(s));
    }
}
